package com.njupt.Array;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/24 15:23
 * @Description: 240. 搜索二维矩阵 II
 * @Version: 1.0
 */


public class SearchMatrix_240 {

    public boolean isFind = false;

    /**
     * 法一：横排竖排各二分查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int index = binarySearch(matrix[i],target);
            if(isFind){
                return true;
            }else {
                for (int k = 0; k < matrix.length; k++) {
                    if(index!= -1 && matrix[k][index] == target){
                        return true;
                    }
                }
            }
        }
        return isFind;
    }

    private int binarySearch(int[] matrix, int target) {
        int left = 0;
        int right = matrix.length-1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(matrix[mid] == target){
                isFind = true;
                return -1;
            } else if (target < matrix[mid]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return right;
    }

    /**
     * 对每一行元素都进行二分查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        for(int[] row : matrix){
            int index = binarySearch1(row,target);
            if(index >= 0){
                return true;
            }
        }
        return false;
    }

    private int binarySearch1(int[] row, int target) {
        int let = 0 ;
        int right = row.length-1;
        while(let <= right){
            int mid = let + (right - let) / 2;
            if(row[mid] == target){
                return mid;
            }else if(target < row[mid]){
                right = mid - 1;
            }else {
                let = mid +1;
            }

        }
        return -1;
    }

    public static void main(String[] args) {
//        int[][] matrix = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};

        int[][] matrix = {{-5}};
        SearchMatrix_240 test = new SearchMatrix_240();
        System.out.println(test.searchMatrix1(matrix, -5));
    }
}
